package algorithm

type Perm struct {
	arr    []int
	result [][]int
}

func (p *Perm) swap(a int, b int) {
	t := p.arr[a]
	p.arr[a] = p.arr[b]
	p.arr[b] = t
}

func (p *Perm) perm(n int, k int) {
	if k >= n {
		var tmp []int
		for _, v := range p.arr {
			tmp = append(tmp, v)
		}
		p.result = append(p.result, tmp)
	}
	for i := k; i < n; i++ {
		p.swap(k, i)
		p.perm(n, k+1)
		p.swap(k, i)
	}
}

func Permutation(n int) [][]int {
	p := Perm{}
	for i := 0; i < n; i++ {
		p.arr = append(p.arr, i)
	}
	p.perm(n, 0)
	return p.result
}
